package b_sorting_advance.a_merge_sort.questions;

import org.junit.Test;

import java.util.Arrays;

/**
 * 逆序对的数量是统计数组随机性的一个指标
 * 数组的随机性越强 逆序对的数量就越多 21345 逆序对21 32145 逆序对 32 31 21
 * 完全随机的数组 逆序对个个数为0 如12345
 * <p>
 * 最简单的解法： 双重迭代，每一个都和前面所有元素比较， 如果小于就计数+1 时间复杂度 ON2
 * <p>
 * 更巧妙的解法： 利用归并排序的合并过程进行判断 时间复杂度ONLogN
 * <p>
 * 比如在归并过程中的两个分别排好序的子数组{2,3,6,8,}和{1,4,5,7,}：
 * 首先1比2小，意味1比2后面的所有元素都小，计数器可直接加4，指向1的下标后移。
 * 4大于2，不考虑，指向2的下标后移。
 * 4大于3，不考虑，指向3的下标后移。
 * 4小于6，意味4比6后面的所有元素都小，计数器可直接加2，指向4的下标后移。
 * 依次类推
 */
public class ReversePairSolution {

    /**
     * 1 递归归并, 对arr[left..right]的范围进行排序
     *
     * @param arr
     * @param left
     * @param right
     */
    private int solve(Comparable[] origArr, int left, int right) {

        Comparable[] arr = Arrays.copyOf(origArr,origArr.length);

        if (left >= right) // 递归结束条件
            return 0;

        int mid = (left + right) / 2; // 小心int类型相加后超出int范围导致bug ..

        return solve(arr, left, mid) + solve(arr, mid + 1, right) + merge(arr, left, mid, right);
    }

    private int merge(Comparable[] arr, int left, int mid, int right) {
        int res = 0;
        Comparable[] aux = Arrays.copyOfRange(arr, left, right + 1);
        for (int i = left; i <= right; i++) {
            aux[i - left] = arr[i];
        }

        int l = left, r = mid + 1;
        for (int c = left; c <= right; c++) {
            if (l > mid) { // 检查 l 的越界问题
                arr[c] = arr[r - left];
                r++;
            } else if (r > right) { // 检查 r 的越界问题
                arr[c] = arr[l - left];
                l++;
            } else if (aux[r - left].compareTo(aux[l - left]) > 0) {
                // 如果左指针的元素更小那么就替换到源数组的c位置, 同时左指针右移一位
                // 注意左指针可能越过mid导致越界问题
                arr[c] = aux[l - left];
                l++;
            } else { // 右边的元素比左边的大
                arr[c] = aux[r - left];
                r++;
                // 这时right比与边所有元素（mid-l+1个）都互为逆序
                res += mid - l + 1;
            }
        }
        return res;
    }

    @Test
    public void testingSortMethod() {
//        Comparable[] arr = {1,2,3,4,5}; // 0
//        Comparable[] arr = {2,1,3,4,5}; // 2= 21
        Comparable[] arr = {3,2,1,4,5}; // 3 = 32 31 21
        int res = solve(arr, 0, arr.length - 1);
        System.out.println(res);
    }
}
